翻訳と辞書
Words near each other
・ Taritu
・ Tariyal
・ Tariyani
・ Tarja
・ Tarja (folk poetry contest)
・ Tarja (island)
・ Tarja Cronberg
・ Tarja Filatov
・ Tarja Halonen
・ Tarja Kallio-Tamminen
・ Tarja Turunen
・ Tarja Turunen discography
・ Tarjadia
・ Tarjagan
・ Tarjali
Tarjan's off-line lowest common ancestors algorithm
・ Tarjan's strongly connected components algorithm
・ Tarjani Vakil
・ Tarjanli
・ Tarjanne
・ Tarje Nordstrand Jacobsen
・ Tarjei Bø
・ Tarjei Dale
・ Tarjei Rygnestad
・ Tarjei Skarlund
・ Tarjei Strøm
・ Tarjei Vesaas
・ Tarjei Vesaas' debutantpris
・ Tarjinder Singh
・ Tarjumo language


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Tarjan's off-line lowest common ancestors algorithm : ウィキペディア英語版
Tarjan's off-line lowest common ancestors algorithm

In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure. The lowest common ancestor of two nodes ''d'' and ''e'' in a rooted tree ''T'' is the node ''g'' that is an ancestor of both ''d'' and ''e'' and that has the greatest depth in ''T''. It is named after Robert Tarjan, who discovered the technique in 1979. Tarjan's algorithm is an offline algorithm; that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired must be specified in advance. The simplest version of the algorithm uses the union-find data structure, which unlike other lowest common ancestor data structures can take more than constant time per operation when the number of pairs of nodes is similar in magnitude to the number of nodes. A later refinement by speeds the algorithm up to linear time.
== Pseudocode ==

The pseudocode below determines the lowest common ancestor of each pair in ''P'', given the root ''r'' of a tree in which the children of node ''n'' are in the set ''n.children''. For this offline algorithm, the set ''P'' must be specified in advance. It uses the ''MakeSet'', ''Find'', and ''Union'' functions of a disjoint-set forest. ''MakeSet(u)'' removes ''u'' to a singleton set, ''Find(u)'' returns the standard representative of the set containing ''u'', and ''Union(u,v)'' merges the set containing ''u'' with the set containing ''v''.
TarjanOLCA(''r'') is first called on the root ''r''.
function TarjanOLCA(u)
MakeSet(u);
u.ancestor := u;
for each v in u.children do
TarjanOLCA(v);
Union(u,v);
Find(u).ancestor := u;
u.colour := black;
for each v such that in P do
if v.colour == black
print "Tarjan's Lowest Common Ancestor of " + u +
" and " + v + " is " + Find(v).ancestor + ".";
Each node is initially white, and is colored black after it and all its children have been visited. The lowest common ancestor of the pair ' is available as ''Find(v).ancestor'' immediately (and only immediately) after ''u'' is colored black, provided ''v'' is already black. Otherwise, it will be available later as ''Find(u).ancestor'', immediately after ''v'' is colored black.
For reference, here are optimized versions of ''MakeSet'', ''Find'', and ''Union'' for a disjoint-set forest:
function MakeSet(x)
x.parent := x
x.rank := 0

function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)
if xRoot.rank > yRoot.rank
yRoot.parent := xRoot
else if xRoot.rank < yRoot.rank
xRoot.parent := yRoot
else if xRoot != yRoot
yRoot.parent := xRoot
xRoot.rank := xRoot.rank + 1

function Find(x)
if x.parent == x
return x
else
x.parent := Find(x.parent)
return x.parent

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Tarjan's off-line lowest common ancestors algorithm」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.